package solutions.jianzhi;

import solutions.lib.BaseSolution;
import solutions.lib.ListNode;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/LGjMqU/">剑指 Offer II 026. 重排链表</a>
 */
public class Solution26 extends BaseSolution {

    public void reorderList(ListNode head) {
        int len = 0;
        ListNode p = head.next;
        while (p != null) {
            len++;
            p = p.next;
        }
        ListNode part2Head = head;
        int ind = 1;
        while (ind <= len / 2) {
            part2Head = part2Head.next;
            ind++;
        }
        p = part2Head.next;
        while (p.next != null) {
            ListNode next = p.next;
            p.next = next.next;
            next.next = part2Head.next;
            part2Head.next = next;
        }
        len /= 2;
        while (len > 0) {
            len--;
            ListNode next = part2Head.next;
            part2Head.next = next.next;
            next.next = head.next;
            head.next = next;
            head = head.next.next;
        }
    }

    public static void main(String[] args) {
        Solution26 solution = new Solution26();
    }
}